/**
 * 
 */
package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName   : Leetcode784 
 * @author      : ganwei 
 * @date        : 2020年5月8日
 * @Description : Leetcode784 784. 字母大小写全排列
 */
public class Leetcode0784 {
	List<String> result = new ArrayList<>();
	int n = 'A'-'a';
	/**
	 * -解题思路，回溯
	 */
    public List<String> letterCasePermutation(String S) {
    	if(S.length() == 0){
    		result.add(S);
    		return result;
    	}
    	backtrack(S,new StringBuilder(),0);
    	return result;
    }
    
    public void backtrack(String S, StringBuilder sb, int index){
    	if(index == S.length()){
    		result.add(sb.toString());
    		return;
    	}
    	
    	if(S.charAt(index)>='0' && S.charAt(index)<='9'){
    		sb.append(S.charAt(index));
    		backtrack(S,sb,index+1);
    		sb.deleteCharAt(sb.length()-1);
    		return;
    	}
    	
    	sb.append(String.valueOf(S.charAt(index)).toLowerCase());
    	backtrack(S,sb,index+1);
    	sb.deleteCharAt(sb.length()-1);
    	
    	sb.append(String.valueOf(S.charAt(index)).toUpperCase());
    	backtrack(S,sb,index+1);
    	sb.deleteCharAt(sb.length()-1);
    	
    }
    
    public static void main(String[] args){
    	Leetcode0784 l784 = new Leetcode0784();
    	String ss = "C";
    	l784.letterCasePermutation(ss);
    	for(String r : l784.result){
    		System.out.println(r);
    	}
    }
}
